'''
Created on Nov 28, 2009 (Finished Dec 9, 2009)
# Problem Set 3 (Part III)
# Name: Noah Spahn
# Collaborators: none
# Time: 8:00 (possibly, but I have no idea)
'''
from string import *

def subStringMatchExact(target,key):
    """ 
    Given a string and substring, returns a tuple of locations of substring found within string
    target: string
    key: sub-string
    """
    start = 0
    position = 0
    tuple = ()
    if len(key)==0:return None
    while position != -1:
        position = find(target,key,start)
        if position >= 0:    tuple = tuple + (position,)
        start = position + len(key)
    return tuple

def constrainedMatchPair(firstMatch,secondMatch,length):
    """
    Given indexes of string matches (n and k) for a key broken into two parts (with one character missing) 
    and the length of the key, return a tuple of the correct matches, where n+m+1==k
    target: string
    key: sub string
    """
    start = 0
    position = 0
    tuple = ()
    if secondMatch and firstMatch != None:
        for n in firstMatch:
            for k in secondMatch:
                if n+length+1==k:
                    tuple=tuple+(n,)
    elif firstMatch == None: # we are dealing with the case of *234, where first char is a variable
        print "nothing provided for firstMatch"
        for k in secondMatch:
            if k !=0: tuple = tuple+(k-1,)
    elif secondMatch == None: # we are dealing with the case of 123*, where last char is a variable
        print "nothing provided for firstMatch"
        for n in firstMatch:
            tuple = tuple+(n,)
    return tuple

# this is a code file that you can use as a template for submitting your solutions

### the following procedure you will use in Problem 3
def subStringMatchOneSub(key,target):
    """
    Search for all locations of key in target, with one substitution
    target: string
    key: sub string
    """
    allAnswers = ()
    for miss in range(0,len(key)):
        # miss picks location for missing element
        # key1 and key2 are substrings to match
        key1 = key[:miss]
        key2 = key[miss+1:]

        print 'breaking key',key,'into key 1:',key1,', key2:',key2
        # match1 and match2 are tuples of locations of start of matches
        # for each substring in target
        match1 = subStringMatchExact(target,key1)
        match2 = subStringMatchExact(target,key2)

        filtered = constrainedMatchPair(match1,match2,len(key1))
        print "filtered:", filtered
        allAnswers = allAnswers + filtered

        print 'possible matches for',key1,key2,'start at',filtered
    return allAnswers

# References
#    http://rene.f0o.com/mywiki/LectureTwo